package test;

import java.util.ArrayList;
//算法：将中缀表达式转换为后缀表达式
/*
* 三个容器
* 一个存储中缀表达式的每一个数字，符号（使用集合arrayList）
* 遍历中缀表达式，数字加直接入后缀表达式 符号入符号栈
* */
public class ReversePolishNotation {
    //通过中缀表达式返回后缀表达式
    public ArrayList<String> reversePolishNotation(String value){
        //中缀表达式
        ArrayList<String> array=getCalculationExpression(value);

        //  符号栈
        Stack02 st1=new Stack02(20);
        //因数字栈没有弹栈操作 使用arrayList代替
        ArrayList<String> st2 =new ArrayList<>();

        for(String allIndext:array){
            //如果是一个数字
            if(allIndext.matches("\\d+")){
                st2.add(allIndext);
            }else if (allIndext.equals("(")){
                st1.push(allIndext);//左括号入符号栈
            }else if(allIndext.equals(")")){
                //弹出符号直到左括号
                while (!st1.peek().equals("(")){
                    st2.add(st1.pop());
                }
                st1.pop();
            }else{

                //符号栈中没有括号--------通过优先级全部弹出符号 存入集合中
                //当前插入符号小于栈顶符号优先级---将栈顶符号弹出
                //栈不为空 同时栈顶符号优先级大于等于当前扫描的符号优先级   例符号栈不为空栈顶为*入栈+优先级小于*
                while(!(st1.topPointer==-1)&&getGrade(st1.peek())>=getGrade(allIndext)){
                    st2.add(st1.pop());
                }
                    st1.push(allIndext);
            }

        }
        //中缀表达式遍历完毕符号栈中还有符号
        while(st1.topPointer!=-1){
            st2.add(st1.pop());
        }
        return st2;
    }
    //返回一个arrayList集合该集合按照顺序存储数据和符号
    public ArrayList getCalculationExpression(String string){
        ArrayList<String> arrayList=new ArrayList<>();

        while (true){
            String value =getdata(string);
            arrayList.add(value);
            string=truncationString(string,value);
            if(string.length()==0){break;}

        }
        return arrayList;
    }
    //输入字符串返回字符串的第一个数值或第一个运算符
    public String getdata(String data){
        String zhi="";
        //遍历字符串每一个字符
        for(int i=0;i<data.length();i++){
            Character ca=data.charAt(i);
            //下标字符是数字
            if(Character.isDigit(ca)){
                zhi=zhi+ca;
            }
            //下标是运算符
            if(!Character.isDigit(ca)){
                //zhi为空串
                if(zhi==""){
                    zhi=ca+"";
                    return zhi;
                }
                //zhi不为空串
                return zhi;

            }
        }
        return zhi;
    }
    //截取字符串
    public String truncationString(String primaryData,String data){
        //截取字符串 从指定下标截取到最后
        String i=primaryData.substring(data.length());
        return i;
    }
    //通过符号返回优先级
    public int getGrade(String value){
        if(value.equals("+")||value.equals("-")){
            return 1;
        }else if (value.equals("*")||value.equals("/")){
            return 2;
        }else {
            return 0;
        }

    }
}
